import java.util.LinkedList;

// 使用深度优先搜索，找出图中于 apex顶点的所有相通的图
public class DepthFirstSearch {
    // 标记图的顶点是否被搜索过
    private boolean[] mark;
    // 记录有多少个顶点和顶点 apex 相连通
    private int count;

    /**
     *
     * @param graph 图对象
     * @param apex 起点顶点
     */
    public DepthFirstSearch(Graph graph, int apex) {
        this.count = 0;
        this.mark = new boolean[graph.getApexNum()];

        // 以 apex 为起点进行深搜
        dfs(graph, apex);
    }

    /**
     * 使用深度优先搜索找出G图中V顶点的所有相通顶点
     * @param g
     * @param v
     */
    public void dfs(Graph g, int v) {
        // 标记已经搜索
        this.mark[v] = true;
        LinkedList<Integer> linkedList = g.adj(v);
        for (int vertex : linkedList) {
            if (!mark[vertex]) {
                // 如果没有搜索过
                dfs(g,vertex);
            }

            System.out.println(v+" ——> "+vertex);

        }
        this.count++;
    }

    /**
     * 判断w顶点于 apex 起点点是否相通
     * @param w
     * @return
     */
    public boolean marked(int w) {
        return this.mark[w];
    }

    /**
     * 获取与顶点 apex 相通的所有顶点的总数
     * @return
     */
    public int getCount() {
        return this.count;
    }

}
